Exercici 1 (Tasca 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
coRE)
Classificació I: propietats bàsiques de les màquines de Turing
Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.
- \{p \mid M_{p}(p)=p\}
- \{p \mid \exists y\ M_{y}(p)=p\}
- \{\langle p,z\rangle \mid \exists y\ M_{p}(y)=z\}
- \{\langle p,z\rangle \mid \exists y\ M_{p}(y)\neq z\}
- \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\uparrow \text{ si i només si } M_q(z)\!\uparrow)\}
- \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\downarrow \text{ si i només si } M_q(z)\!\uparrow)\}